package leetcode.code1263;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int m, n;
	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };
	int[] o = new int[] { 0, 1, 0, -1, 1, 0, -1, 0 };
	char[][] grid;

	public int minPushBox(char[][] grid) {
		this.grid = grid;
		int[] box = null;
		int[] target = null;
		int[] player = null;
		m = grid.length;
		n = grid[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = grid[i][j];
				if (cur == 'B') {
					box = new int[] { i, j };
					this.grid[i][j] = '.';
				} else if (cur == 'T') {
					target = new int[] { i, j };
					this.grid[i][j] = '.';
				} else if (cur == 'S') {
					player = new int[] { i, j };
					this.grid[i][j] = '.';
				}
			}
		}
		boolean[][] flags = new boolean[m * n][m * n];
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
		this.grid[box[0]][box[1]] = '#';
		for (int i = 0; i < 8; i += 2) {
			int nextx = box[0] + d[i], nexty = box[1] + d[i + 1];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && this.grid[nextx][nexty] == '.') {
				boolean[] beens = new boolean[m * n];
				if (dfs(player[0], player[1], nextx, nexty, beens)) {
					flags[index(box[0], box[1])][index(nextx, nexty)] = true;
					queue.add(new int[] { box[0], box[1], 0, nextx, nexty });
				}
			}
		}
		this.grid[box[0]][box[1]] = '.';
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			if (cur[0] == target[0] && cur[1] == target[1]) {
				return cur[2];
			}
			add(flags, queue, cur, cur[2]);
		}
		// MaxArrays
		return -1;
	}

	private boolean dfs(int sx, int sy, int tx, int ty, boolean[] flags) {
		if (sx == -1 && sy == -1) {
			return true;
		}
		if (sx < 0 || sx == m || sy < 0 || sy == n || this.grid[sx][sy] == '#' || flags[this.index(sx, sy)]) {
			return false;
		}
		if (sx == tx && sy == ty) {
			return true;
		}
		flags[index(sx, sy)] = true;
		for (int i = 0; i < 8; i += 2) {
			int nextx = sx + d[i], nexty = sy + d[i + 1];
			if (dfs(nextx, nexty, tx, ty, flags)) {
				return true;
			}
		}
		return false;
	}

	public int index(int i, int j) {
		return i * n + j;
	}

	private void add(boolean[][] flags, PriorityQueue<int[]> queue, int[] start, int cnt) {
		int x = start[0], y = start[1];
		int fx = start[3], fy = start[4];
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			int otherx = x + o[i], othery = y + o[i + 1];
			int nextIndex = this.index(nextx, nexty);
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && this.grid[nextx][nexty] == '.'
					&& !flags[nextIndex][index(fx, fy)] && otherx >= 0 && otherx < m && othery >= 0 && othery < n
					&& this.grid[otherx][othery] == '.') {
				boolean[] beens = new boolean[m * n];
				this.grid[x][y] = '#';
				if (dfs(fx, fy, otherx, othery, beens)) {
					flags[nextIndex][index(fx, fy)] = true;
					queue.add(new int[] { nextx, nexty, cnt + 1, x, y });
				}
				this.grid[x][y] = '.';
			}
		}
	}

	@Override
	public void debug4() {
		H.compare(8, this.minPushBox(H.str2array5(
				"[[\"#\",\".\",\".\",\"#\",\"T\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\".\",\".\",\"#\",\".\",\"#\",\".\",\".\",\"#\"],[\"#\",\".\",\".\",\"#\",\".\",\"#\",\"B\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\".\",\".\",\".\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\".\",\"#\",\".\",\"S\",\"#\"],[\"#\",\".\",\".\",\"#\",\".\",\"#\",\"#\",\"#\",\"#\"]]")));
		H.compare(7, this.minPushBox(H.str2array5(
				"[[\"#\",\".\",\".\",\"#\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\".\",\".\",\"T\",\"#\",\".\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\"#\",\"B\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\".\",\".\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\"#\",\".\",\"S\",\"#\"],[\"#\",\".\",\".\",\"#\",\"#\",\"#\",\"#\",\"#\"]]")));
		H.compare(3, this.minPushBox(H.str2array5(
				"[[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\"T\",\"#\",\"#\",\"#\",\"#\"],[\"#\",\".\",\".\",\"B\",\".\",\"#\"],[\"#\",\".\",\"#\",\"#\",\".\",\"#\"],[\"#\",\".\",\".\",\".\",\"S\",\"#\"],[\"#\",\"#\",\"#\",\"#\",\"#\",\"#\"]]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
